KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

3. lecke: Különböző feladatok megoldása szimplex módszerrel

|  | Módosított normálfeladat, általános feladat, maximum feladat megoldása szimplex módszerrel. Minimumfeladatok megoldási módszerei. Dualitás fogalma.
| Tanulási útmutató
| Ez a lecke szorosan kapcsolódik az előző leckéhez. Csak akkor foglalkozzon ezzel, ha az előző feladatokat jól, hibátlanul megoldotta és megértette a szimplex táblázat lényegét. Azért nem az előző leckében tárgyaljuk ezeket az eseteket, mert idő kell a szimplex módszer lényegének megértéséhez.
| Tevékenységek
| Figyelmesen tanulmányozza át a tankönyv 1.5.2. alfejezetét. Különösen fontos, hogy jól értse a szimplex táblázat jelentéseit: Milyen szerepe van az egyenlőségek esetén az u* hiányváltozónak és a z* segéd-célfüggvénynek. A megértés szempontjából a szinte minden szónak fontos jelentése van. Kövesse végig figyelmesen a tankönyvben található feladat megoldását, majd csukja be a tankönyvet és önállóan is gondolja végig a megteendő lépéseket. Az általános maximum feladat megoldása már csak egy plusz lépés megtételét jelenti: a v többletváltozó bevezetését. A bemutatott feladatot önállóan, külön lapon is oldja meg! A bázis-transzformáció után mindig értékelje a kapott szimplex táblázatot: leolvasható-e egy lehetséges megoldás? ez a lehetséges megoldás optimális-e? a célfüggvény korlátos-e? alternatív optimális megoldást kaptunk-e? Az eredménynek megfelelően tegye meg a szükséges további lépéseket és adja meg a lehetséges válaszokat. Ezek a logikai műveletek minősítik a diplomás embert! Ilyeneket kell gyakran végezni majd a munkahelyen is! Figyelmesen olvassa el a minimumfeladatok megoldásának gondolatmenetét. Jól jegyezze meg, hogyan lehet a minimumfeladatot visszavezetni maximum feladatra és megoldani az eddig tanult módon. A dualitás elvének nagy jelentősége van a lineáris programozási feladatok megoldásában. A dualitás fogalma és gazdasági értelmezése, valamint a felhasználás elvei a tankönyvben találhatók. Tanulmányozza figyelmesen ezeket az oldalakat, mert az érzékenységvizsgálatnál nagy hasznát veheti. A dualitással kapcsolatos kérdések és példák a tankönyv 2.6. fejezetében találhatók. Gyakorlásként oldja meg ezeket!
| Követelmények
| Fel tudja ismerni, hogy a megoldandó feladat milyen típusú, és ennek megfelelően fel tudja írni az induló szimplex táblázatot. El tudja dönteni, hogy hol kell bevezetni az u* hiány és v többletváltozót. Elő tudja állítani a z* segéd-célfüggvényt. Önállóan el tudja végezni a bázis-transzformációkat: ki tudja megválasztani a generáló elemet, és hibátlanul el tudja végezni a szükséges számításokat. Értelmezni tudja az új táblázatokat. El tudja dönteni, hogy milyen megoldással áll szemben, hogyan kell folytatni a lépéssorozatot. A táblázatról le tudja olvasni a kapott eredményt, és hogyan kell azt közölni. Fel tudja írni egy feladat duál párját. A szimplex táblázatból le tudja olvasni mind a prímál mind a duál feladat optimális megoldását.

|  | Önellenőrző feladatok
| 1. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel!
| x 1 , x 2 , x 3 ≥ 0 x 1 +3 x 2 + x 3 ≥ 12 x 1 +2 x 2 + x 3 = 10 z=20 x 1 +30 x 2 +40 x 3 → max⁡
| Vegyen elő egy négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a B 0 táblázat. Írja be az alábbi mezőkbe a kapott értékeket! Ahol nincs elem, oda tegye "-" jelet.
| a) Írja ide a B 0 táblázat z* sorának elemeit:
z* |  |  |  |  |
| b) Végezze el a bázis-transzformációt, amelynek eredménye a B 1 táblázat. Válasszon generáló elemet a 3. oszlopból! Írja ide a B 1 táblázat utolsó két sorának elemeit:
-z |  |  |  |  |
z* |  |  |  |  |
| c) Értékelje a B 1 -es táblázatot, és döntse el, hogy az alábbi állítások helyesek-e!
Itt leolvasható egy alternatív optimum. |
Itt leolvasható egy lehetséges megoldás. |
| d) Értékelje a B 1 -es táblázatot, és döntse el, hogy az alábbi állítások helyesek-e!
Itt még nem olvasható le egy lehetséges megoldás. |
Itt a célfüggvény nem korlátos esete áll fenn! |
| e) Oldja meg a feladatot, és írja ide az optimális megoldást, ha létezik! Az optimális megoldás: x 1 = x 2 = x 3 = z =
| 2. Egy lineáris programozási feladat megoldása során eljutottunk a B 2 táblázathoz.
| a) Értékelje a táblázatot! Döntse el, hogy melyik állítás igaz!
Az eredeti modell egy módosított maximum feladat volt. |
Az eredeti modell egy módosított minimum feladata volt |
Az eredeti modell egy általános minimum feladat volt. |
A B 2 -ből látszik, hogy a célfüggvény nem korlátos. |
A B 2 -ből látszik, hogy alternatív optimum van. |
| b) Az optimális megoldást: x 1 = x 2 = x 3 = z =
| c) Alternatív optimuma van: x 1 = x 2 = x 3 = z =
| d) Egy másik alternatív optimum: x 1 = x 2 = x 3 = z =
| 3. Oldja meg a duál párján keresztül az alábbi lineáris programozási feladatot!
| x 1 , x 2 , x 3 ≥ 0 x 1 + x 2 + x 3 ≥ 50 2 x 1 + x 2 ≥ 20 z=20 x 1 +18 x 2 +8 x 3 → min⁡
| Vegyen elő egy négyzetrácsos lapot! Írja fel a feladat duál párját! A duál változót jelölje y-nal. Helyezze el ezt a modellt a szimplex táblázatban. Legyen ez a B 0 táblázat! Végezzen bázis-transzformációt! Ellenőrzéshez tegye a következőt:
| a)Töltse ki a következő táblázatot a duál feladat adataival!
B 0 | y 1 | y 2 |
x 1 |  |  |
x 2 |  |  |
x 3 |  |  |
−z |  |  |
| b) Végezze el a szükséges bázis-transzformációkat és írja fel a primál feladat optimális megoldását: x 1 = x 2 = x 3 = z o p t =
| c) duál feladat optimális megoldása: y 1 = y 2 = z o p t =